package com.lyz.dataStructure.LeetCode.dongtaiguihua.beibao;

import javafx.scene.SceneAntialiasing;

import java.util.Scanner;

/**
 *@Author:759057893@qq.com Lyz
 *@Date: 2019/7/31 21:46
 *@Description:
 **/

// leetcode 分割等和子集
public class Solution1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String[] st = s.split(" ");
        int[] arr = new int[st.length];
        for(int i =0;i<arr.length;i++){
            arr[i] = Integer.parseInt(st[i]);
        }
        System.out.println( canPartition(arr));
    }

   /* public static boolean canPartition(int[] nums) {
        int size = nums.length;

        int s = 0;
        for (int num : nums) {
            s += num;
        }

        // 特判 2：如果是奇数，就不符合要求
        if ((s & 1) == 1) {
            return false;
        }

        int target = s / 2;

        // 创建二维状态数组，行：物品索引，列：容量
        boolean[][] dp = new boolean[size][target + 1];
        // 先写第 1 行
        for (int i = 1; i < target + 1; i++) {
            if (nums[0] == i) {
                dp[0][i] = true;
            }
        }
        for (int i = 1; i < size; i++) {
            for (int j = 0; j < target + 1; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= nums[i]) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }
            }
        }
        return dp[size - 1][target];
    }*/
       public static boolean canPartition(int[] nums) {
           int s = sum(nums);
           if(s%2!=0){
               return false;
           }
           int w = s/2;
           boolean[] dp = new boolean[w+1];
           dp[0] = true;
           for(int num:nums){
               for(int i =w;i>=num;i--){
                   dp[i] = dp[i] || dp[i-num];
               }
           }
           return dp[w];


       }
       public static int sum(int[] nums){
           int s =0;
           for(int num : nums){
               s =s +num;
           }
           return s;
       }
}

